\subsubsection{Übung (i) - \buchmann{15.5.1}}
\paragraph{Aufgabe}
Sei $p$ eine Primzahl, $g$ eine Primitivwurzel $\mod{p}, a \in \{0,1,\dotsc,p-2\}$ und $A\equiv g^a\mod{p}$. Beschreiben Sie einen Zero-Konwledge-Beweis dafür, dass Alice den diskreten Logarithmus $a$ von $A\mod{p}$ zur Basis $g$ kennt. Der ZK-Beweis ist analog zu dem in Abschnitt 15.4.3. beschriebenen.

\paragraph{Lösung}
Der öffentliche Schlüssel ist $(A,p,g)$, der geheime private Schlüssel von Alice ist $a$

Eine Runde des Zero-Knowledge-Beweises sieht wie folgt aus:

\begin{enumerate}
\item \textbf{Commitment} Der Beweiser Alice wählt zufällig und gleichverteilt einen Exponenten $b \in \{0,1,\dotsc,p-2\}$. Sie berechnet $B\equiv g^b\mod{p}$ und schickt $B$ an den Verifizierer Bob
\item \textbf{Challenge} Bob wählt zufällig und gleichverteilt ein $e \in \{0,1\}$ und sendet es an Alice.
\item \textbf{Response} Alice berechnet $y=b+ea\mod{p-1}$ und sendet es zur Identifikation an Bob.\footnote{%
Die prime Restklassengruppe $(\Z/p\Z)^{*}$, bezeichnet mit $G$, ist eine endliche zyklische Gruppe. Daher gilt $a^b = a^{b\mod |G|}$. Für die Ordnung der primen Restklassengruppe $G$ gilt $|G|=p-1$. Da $y$ als Exponent verwendet wird, kann es also $\mod{p-1}$ genommen werden.}
\item Bob verifiziert, dass $g^y\equiv A^eB\mod{p}$ und bestätigt somit Alice' Identität.
\end{enumerate}

Es handelt sich um einen Zero-Knowledge-Beweis:

Würde ein Betrüger versuchen, sich zu Identifizieren, ohne Kenntnis vom geheimen Schlüssel $a$ zu haben, müsste er $B$ aus einem festen $y$ berechnen: $$g^y\equiv A^eB\mod{p}$$ $$g^yA^{-e}\equiv B\mod{p}$$
Ein Betrüger kann also nur für ein $e$ die Lösung kennen. 

\begin{description}
\item[1. Fall $e=0$] Der Betrüger kennt ein $y$ für das gilt $g^y\equiv A^0B\mod{p}$, also den DL von $B$ zur Basis $g$.
\item[2. Fall $e=1$] Der Betrüger kennt ein $y$ für das gilt $g^y\equiv A^1B\mod{p}$, also den DL von $AB$ zur Basis $g$.
\end{description}

Er kann jedoch nie beide Fragen beantworten. Der Betrüger kann nur mit der Wahrscheinlichkeit $\frac{1}{2}$ betrügen. 

Die Vollständigkeit und Korrektheit des Protokolls ist damit gegeben.

Das Protokoll kann auch simuliert werden. Man wählt zufällig gleichverteilt $y \in \{0,1,\dotsc,p-2\}, e \in \{0,1\}$. Nun setzt man $B = g^yA^{-e}\mod{p}$. Das Protokoll wird hiermit funktionieren und auch die Wahrscheinlichkeitsverteilung der Protokollnachrichten ist dieselbe wie beim Originalprotokoll.